package 二叉树题目.重建二叉树;

public class Solution {
    public int i = 0;

    public TreeNode reConstructBinaryTree(int[] pre, int[] vin) {
       return reConstructBinaryTreeChild(pre,vin,0, vin.length-1);
    }

    public TreeNode reConstructBinaryTreeChild(int[] pre, int[] vin, int inbegin, int inend) {
        if (inbegin > inend){
            return null;
        }
        // 前序遍历第一个为根节点
        TreeNode root = new TreeNode(pre[i]);
        // 在中序遍历中找到根节点
        int rootIndex = findIndex(vin, inbegin, inend, pre[i]);
        i++;
        root.left = reConstructBinaryTreeChild(pre, vin, inbegin, rootIndex - 1);
        root.right = reConstructBinaryTreeChild(pre, vin, rootIndex + 1, inend);
        return root;
    }

    private int findIndex(int[] vin, int inbegin, int inend, int key) {
        for (int j = inbegin; j <= inend; j++) {
            if (vin[j] == key){
                return j;
            }
        }
        return -1;
    }
}
